package 牛客.哈希;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和 {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //双指针
        if (num.length<3) {
            return new ArrayList<>();
        }

        ArrayList<ArrayList<Integer>> lists=new ArrayList<>();
        Arrays.sort(num);
        for (int i = 0; i <num.length; i++) {
            //1.对于排好序的元素，当前它大于0，那么后面的两个数不会再符合 三数之和为0 的条件
            if (num[i]>0) {
                continue;
            }
            //2.当前元素和上一个元素的值相同，那么就结束本轮循环
            if (i>0 && num[i]==num[i-1]) {
                continue;
            }
            int a=num[i];
            int p1=i+1;
            int p2=num.length-1;
            while (p1<p2) {
                int sum=a+num[p1]+num[p2];
                //对sum进行判断
                if (sum==0) {
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(a);
                    list.add(num[p1]);
                    list.add(num[p2]);

                    lists.add(list);

                    //对已经找的三个数要进行进一步的判断
                    while (p1<p2 && num[p1]==num[p1+1]) {
                        //对左指针的下一个元素进行判断，如果和当前左指针元素相同则要++
                        p1++;
                    }
                    while (p1<p2 && num[p2]==num[p2-1]) {
                        //对右指针的上一个元素进行判断，如果和当前右指针元素相同则要--
                        p2--;
                    }
                    p1++;
                    p2--;
                }else if (sum<0) {
                    //sum小于0，那么左指针++
                    p1++;
                }else {
                    //sum大于0，那么右指针--
                    p2--;
                }
            }
        }
        return lists;

    }
}
